//
// Created by 高炎 on 2024/7/28.
// 实现的是升序排序
// 算法描述详见博客:https://blog.csdn.net/qq_44616044/article/details/115708056;
//
#include <iostream>
#include <vector>
using namespace std;
void InsertSort(vector<int> &arr)
{
    int temp;
    int j;
    for (int i = 1; i < arr.size(); i++)
    // i 从 1 开始，因为 0 号元素默认是有序的
    {
        if (arr[i] < arr[i - 1])
        {
            // 需要插入
            temp = arr[i];
            for (j = i - 1; j >= 0 && arr[j] > temp; j--)
            // 从待插入元素前一个开始，往前遍历，直到找到比待插入元素小的元素
            {
                arr[j + 1] = arr[j]; // 将大于 temp 的元素往后移动一个位置
            }
            arr[j + 1] = temp; // 注意这里是 j + 1，因为 j 最后一次循环的时候是 j-- 的;也就是说 j 当前所指的位置比 temp 小，需要插入到当前所指位置的下一个位置
        }
    }
}

int main()
{
    vector<int> arr = {4, 3, 99, 7, 9};
    for (int i = 0; i < arr.size(); i++)
    {
        cout << arr[i] << ",";
    }
    cout << endl;
    InsertSort(arr);
    for (int i = 0; i < arr.size(); i++)
    {
        cout << arr[i] << ",";
    }
    cout << endl;

    return 0;
}